"""
难度：中等
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
"""


"""
解题思路：
矩阵是有序的，可以考虑使用二分搜索来进行查找。

迭代对角线元素，假设对角线元素的坐标为 (row, col)。把数组元素按对角线分为右上角部分和左下角部分。

则对于当前对角线元素右侧第 row 行、对角线元素下侧第 col 列进行二分查找。

如果找到目标，直接返回 True。
如果找不到目标，则缩小范围，继续查找。
直到所有对角线元素都遍历完，依旧没找到，则返回 False。
"""
from typing import List


class Solution:
    def digonalBinarySearch(self,matrix,diagonal,target):
        left = 0
        right = diagonal

        while left < right:
            mid = left + (right - left)//2
            if matrix[mid][mid] <target:
                left = mid +1
            else:
                right =mid
        return left

            

    def rowBinarySearch(self,matrix,begin,cols,target):
        left = begin
        right = cols
        while left < right:
            mid = left + (right-left)//2
            if matrix[mid][mid] <target:
                left = mid +1
            elif matrix[begin][mid] > target:
                right = mid -1
            else:
                left = mid
                break
        return begin <= left <= cols and matrix[begin][left] == target
    
    def colBinarySearch(self,matrix,begin,rows,target):
        left = begin+1
        right = rows
        while left < right:
            mid = left +(right - left)//2
            if matrix[mid][begin] < target:
                left = mid+1
            elif matrix[mid][begin] >target:
                right = mid -1
            
            else:
                left = mid
                break
        return begin <= left<= rows and matrix[left][begin] == target

    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        rows = len(matrix)
        if rows == 0:
            return False
        cols = len(matrix[0])
        if cols == 0:
            return False

        min_val = min(rows, cols)
        index = self.diagonalBinarySearch(matrix, min_val - 1, target)
        if matrix[index][index] == target:
            return True
        for i in range(index + 1):
            row_search = self.rowBinarySearch(matrix, i, cols - 1, target)
            col_search = self.colBinarySearch(matrix, i, rows - 1, target)
            if row_search or col_search:
                return True
        return False
